// https://www.lintcode.com/problem/427/

class Solution {
public:
    /**
     * @param n: n pairs
     * @return: All combinations of well-formed parentheses
     */

    vector<string> generateParenthesis(int n) {
        vector<string> res;
        string s;
        helper(s, res, 0, 0, n);
        return res;
    }

    // 法一：
    // 如果当前右括号数量等于括号对数 n, 那么当前字符串即是一种组合, 放入解中.
    // 如果当前左括号数量等于括号对数 n, 那么当前字符串后续填充满右括号, 即是一种组合.
    // 如果当前左括号数量未超过 n:
        // 如果左括号多于右括号, 那么此时可以添加一个左括号或右括号, 递归进入下一层
        // 如果左括号不多于右括号, 那么此时只能添加一个左括号, 递归进入下一层

    // void helper(string s, vector<string> &res, int l, int r, int n) {
    //     if (r == n) {
    //         res.push_back(s);
    //     }
    //     else if(l == n) {
    //         s += string(n - r, ')');
    //         res.push_back(s);
    //     }
    //     else {
    //         if (l > r)
    //             helper(s + ')', res, l, r + 1, n);
    //         helper(s + '(', res, l + 1, r, n);
    //     }
    // }

    // 法二：剪枝条件：l > n || r > n || r > l
    void helper(string s, vector<string>& res, int l, int r, int n) {
        if (l > n || r > n || r > l) return;
        if (l == n && r == n) {
            res.push_back(s);
            return;
        }
        helper(s + '(', res, l + 1, r, n);
        helper(s + ')', res, l, r + 1, n);
    }
};